package me.zk.practice1.s;

/**
 * @author zhangkai
 * @date 2023/7/15 12:52
 */
public class LS_Offer_26 {

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null ||B == null) {
            return false;
        }
        return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
     /*
    判断B是否为A的子结构,其中B子结构的起点为A的根节点
    */
     private boolean recur(TreeNode A, TreeNode B) {
         // 若B走完了,说明查找完毕,B为A的子结构
        if (B == null) {
            return true;
        }
         // 若B不为空并且A为空或者A与B的值不相等,直接可以判断B不是A的子结构
        if (A == null || A.val != B.val) {
            return false;
        }
         // 当A与B当前节点值相等,若要判断B为A的子结构
         // 还需要判断B的左子树是否为A左子树的子结构 && B的右子树是否为A右子树的子结构
         // 若两者都满足就说明B是A的子结构,并且该子结构以A根节点为起点
        return recur(A.left,B.left) && recur(A.right,B.right);
     }
}
